//
//  Sort_12.swift
//  ArithmeticClass7
//
//  Created by xiangzuhua on 2020/10/20.
//  Copyright © 2020 xiang. All rights reserved.
//

import Foundation

public class Sort_12: NSObject {
    // 归并排序
    class func merge_sort(_ arr: inout[Int]){
        let count = arr.count
        merge_sort_C(&arr, n: 0, m: count - 1)
    }
    
    class func merge_sort_C(_ arr: inout[Int], n: Int, m: Int) {
        if n >= m {
            return
        }
        let p = n + (m - n) / 2
        merge_sort_C(&arr, n: n, m: p)
        merge_sort_C(&arr, n: p + 1, m: m)
        merge(&arr, n...p, p+1...m)
    }
    
    class func merge(_ arr: inout[Int], _ rangeHead: CountableClosedRange<Int>, _ rangeEnd: CountableClosedRange<Int>) {
        var i_h = rangeHead.first!
        let i_e = rangeHead.last!
        var j_h = rangeEnd.first!
        let j_e = rangeEnd.last!
        
        var tempArr = [Int](repeating: 0, count: rangeHead.count + rangeEnd.count)
        var k = 0
        while i_h <= i_e && j_h <= j_e{
            if arr[i_h] <= arr[j_h] {
                tempArr[k] = arr[i_h]
                k += 1
                i_h += 1
            } else {
                tempArr[k] = arr[j_h]
                k += 1
                j_h = j_h + 1
            }
        }
        
        // 判断那个子数组中有剩余的数据
        var start: Int = i_h
        var end: Int = i_e
        if j_h <= j_e {
            start = j_h
            end = j_e
        }
        
        // 将剩余的数据拷贝到临时数组
        while start <= end {
            tempArr[k] = arr[start]
            k += 1
            start += 1
        }
        
        // 将tempArr拷贝到arr中
        if rangeEnd.count + rangeHead.count == tempArr.count {
            var i: Int = 0
            for index in rangeHead.lowerBound...rangeEnd.upperBound {
                arr[index] = tempArr[i]
                i = i + 1
            }
        }
    }
    
    
    // 快速排序
    class func quick_sort(_ arr: inout [Int]){
        let count = arr.count
        quick_sort_c(&arr, n: 0, m: count - 1)
    }
    
    class func quick_sort_c(_ arr: inout [Int], n: Int, m: Int){
        if n >= m {
            return
        }
        
        let q = partition(&arr, n: n, m: m)
        quick_sort_c(&arr, n: n, m: q - 1)
        quick_sort_c(&arr, n: q + 1, m: m)
    }
    
    class func partition(_ arr: inout[Int], n: Int, m: Int) -> Int{
        let pivot = arr[m]
        var i = n
        for index in n...m - 1 {
            if arr[index] < pivot{
                let temp = arr[index]
                arr[index] = arr[i]
                arr[i] = temp
                i += 1
            }
        }
        arr[m] = arr[i]
        arr[i] = pivot
        
        return i
    }
    
    // 快排查找第K大的元素
    class func LookForKthLargestElement(_ arr: inout[Int],k: Int) -> Int{
        let count = arr.count
        // 寻找第K大的元素，对于一个有序的数组，就是倒数第三位，也就是顺数第 m + 1 - k 位数
        let target = count - k
        let p = LookForKthLargestElement_c(&arr, n:0, m: count - 1,k: target)
        return p
    }
    
    class func LookForKthLargestElement_c(_ arr: inout [Int], n: Int, m: Int, k: Int) -> Int{
        if n >= m {
            return arr[n]
        }
        
        let i = self.partition(&arr, n: n, m: m)
        if i == k {
            return arr[i];
        }
        
        if i > k {
            return LookForKthLargestElement_c(&arr, n: n, m: i - 1, k: k)
        } else {
            return LookForKthLargestElement_c(&arr, n: i + 1, m: m, k: k)
        }
    }
}
